今天來寫第15題

題目

題目翻譯

給一包含n個整數的陣列nums，有任意三個元素a, b, c能夠使a + b + c = 0 成立嗎？找到所有陣列中的三個數，相加總和為零。
提示：答案中不可有重複的組合。

解題步驟

1. 處理空陣列和極端情況：

   • 首先檢查陣列大小是否小於 3。如果是，直接返回空結果，因為不可能有三個數字可以求和為 0。

2. 排序數組：

   • 將輸入數組進行排序，這有助於方便地進行雙指針（Two Pointers）技術來查找三元組。

3. 遍歷數組：

   • 使用一個 for 循環來逐個選擇每個元素 nums[i] 作為三元組中的第一個元素。
   • 對於每個 nums[i]，計算目標和 target = -nums[i]，並使用雙指針技術在剩餘數組中找到另外兩個數字，其和為 target。

4. 雙指針技術：

   • 設置兩個指針，left 指向 i 之後的數字，right 指向數組末尾。
   • 如果 nums[left] + nums[right] == target，找到一個符合條件的三元組，並將其添加到結果中。隨後移動指針，並跳過重複的數字，避免重複結果。
   • 如果和大於目標，則將 right 指針左移，縮小和；如果和小於目標，則將 left 指針右移，增大和。

5. 跳過重複元素：

   • 為了避免重複的三元組，當前後元素相同時，直接跳過這些重複的數字。

6. 返回結果：

   • 最後返回找到的所有符合條件的三元組。

code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        if (nums.size() < 3) return ans;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size() - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 避免重複

            int target = -nums[i];
            int left = i + 1, right = nums.size() - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++; // 跳過重複元素
                    while (left < right && nums[right] == nums[right - 1]) right--; // 跳過重複元素
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }
};